Транзакции - 1

Максимальная оценка за эту задачу — 60 баллов, на проверку необходимо сдавать программу, решающую задачу

Для ускорения работы файловой системы на сервере необходимо накапливать операции ввода-вывода (транзакции) в буфере, а затем выполнять их.

Всего в буфере накоплено $n$ транзакций, пронумерованных от $1$ до $n$. Память сервера состоит из $m$ участков, пронумерованных от $1$ до $m$. Для каждой транзакции известно множество участков памяти, из которых данная транзакция производит чтение, и множество участков памяти, в которые она производит запись. Для $i$-й транзакции обозначим эти множества как $RS_i$ и $WS_i$.

Из заданного множества транзакций нужно выбрать некоторое подмножество и упорядочить транзакции внутри него.

Пусть было выбрано упорядоченное подмножество (последовательность) из $k$ транзакций с номерами $p_1, p_2, \ldots, p_k$. В выбранной последовательности транзакций не должно быть конфликтов. Конфликтом называется пара транзакций, в которой более ранняя транзакция записывает данные в область памяти, из которого затем читает другая транзакция. Более формально, транзакции $p_i$ и $p_j$, где $i < j$, конфликтуют, если существует такой участок памяти $l$, что $l \in WS_{p_i}$ и $l \in RS_{p_j}$.

По данному множеству транзакций вам нужно выбрать из него последовательность транзакций наибольшей возможной длины, не содержащей конфликтов. Вам не требуется находить оптимальное решение в данной задаче. Ваше решение получит количество баллов, пропорциональное длине найденной вами последовательности транзакций.